Sipser CH2 Exercises' Answer 2.1-2.17

2.2

• a.Construct PDA to recognize A and B，for ,use pumping lemma, easily know is not CFL.
• b.,if CFL is closed under complementation, then it's closed under intersection .Contradiction!

2.4

• a.
• b.
• c.
• d.
• e.
• f.

2.5

考察CFG转化PDA，具体流程见教材，过于繁琐此处略

2.6

• a.
• b
• c.
• d.

2.9

• 考虑,会有两个最左推导，故而歧义

2.10

This language is recognized by a non-deterministic pushdown automaton (NPDA) that initially guesses which of the two conditions to verify: that the number of ''s equals the ''s (), or that the ''s equal the ''s (). For the first path, it uses the stack to count ''s by pushing symbols, then matches them by popping for each '', while ignoring subsequent ''s. For the second path, it ignores all ''s, pushes symbols for each '', and then pops them for each ''. The string is accepted if either of these computational paths successfully consumes the entire input and concludes with an empty stack.

2.11，2.12

均为CFG转化PDA，详见教材

2.13

is the set of strings over alphabet ,that satisfy one of the following two conditions: - The string contains exactly two instances of ,with any number of ,placed anywhere. - The string contains exactly one instance of ,and the number of following the is exactly twice the number of preceding it.

假设is regular，已知 is regular.则is regular.对应用泵引理，得到矛盾

2.14

2.15

考虑,.无法生成

2.16

• ​ 由 CFG  生成，即 
• ​ 由 CFG  生成，即 
• Union:添加
• Concatenation:添加
• Star:添加

2.17

• 利用归纳法
  • 基本情况：,可以构造CFG
  • 归纳假设：正则语言是由基本情况的正则运算组合构成的，而CFL在正则运算下封闭，故正则语言都是CFL
• 示例：将 RE (a+b)*c 转换为 CFG
  • :
  • :
  • :